/* Universidad del Valle de Guatemala
 * Mariana Castillo, 12319
 * Julio Maldonado, 12377
 * Seccion 30, Algoritmos y Estructura de Datos
 * Algoritmo de Floyd
 */
package hoja9;

import java.io.IOException;
public class Floyd {
    ArchivoTexto a= new ArchivoTexto();
    Grafo graf;
    int[][] P;
    int[] max;
    int centro;
    int minimo=20000;     
  
    public Floyd(){
        
        try {
            
            a.getArchivo();
            a.VerticesGrafo(); // Nombre de los nodos
            graf = a.matrizPesos(); // Peso de los arcos entre nodos
            P = new int[30][30]; // Matriz de nodos intermedios
            max = new int[30];
        } catch (IOException ex) {
            ex.printStackTrace();
        }
        for(int n=0;n<a.grafo.size();n++){
            for(int m=0;m<a.grafo.size();m++){
                P[n][m]=20000;
            }
        }
    }
    
    /**
     * Algoritmo de Floyd para encontrar el camino mas corto entre todos los nodos
     * Basado en la presentacion de clase
     * Pre: existe una matriz de adyacencia con los valores iniciales del grafo
     * Post: matriz de adyacencia con los valores mas pequeños entre cada nodo
     * No hay parametros
     */
    public void caminoCorto(){
        for(int k=0;k<graf.size();k++){
            for(int i=0;i<graf.size();i++){
                for(int j=0;j<graf.size();j++){
                    if(graf.getEdge(graf.get(i),graf.get(j))>(graf.getEdge(graf.get(i), graf.get(k))+graf.getEdge(graf.get(k), graf.get(j)))){
                        graf.addEdge(graf.get(i), graf.get(j), (graf.getEdge(graf.get(i), graf.get(k))+graf.getEdge(graf.get(k), graf.get(j))));
                        P[i][j]=k;
                    }
                }
            }
        }
        
    }
    
    /**
     * Encontrar el centro del grafo
     * Pre: matriz de adyacencia con los menores valores entre cada nodo
     * Post: centro del grafo
     * No hay parametros ni valor de retorno
     */
    public void centroGrafo(){
        caminoCorto();
        int n=0;       
        // Encontrar los maximos de cada columna de la matriz
        for(int i=0;i<graf.size();i++){
            for(int j=0;j<graf.size()-1;j++){
                int num1=graf.getEdge(graf.get(j), graf.get(i));
                n=j;
                n++;
                int num2=graf.getEdge(graf.get(n), graf.get(i));
                if(num1>num2){
                    max[i]=num1;
                }
                else{
                    max[i]=num2;
                }
            }
            n++;
        }
        // Encontrar el minimo de los maximos de cada columna
        for(int i=0;i<graf.size();i++){
            int num1=max[i];
            if(num1<minimo){
                centro=i;
                minimo=num1;
            }
        }
        System.out.println("\nEl centro del grafo es: "+graf.get(centro)+"\n");
        
    }
    
    /**
     * Desplegar los nodos intermedios al obtener la ruta mas corta
     * Pre: no hay
     * Post: nodos intermedios desplegados
     * No hay valor de retorno
     * @param num1
     * @param num2
     */
    public void mostrarIntermedias(int num1, int num2){
        if(P[num1][num2]!=20000){
            mostrarIntermedias(num1,P[num1][num2]);
            System.out.print(", "+graf.get(P[num1][num2]));
            mostrarIntermedias(P[num1][num2],num2);
            return;
        }
        else return;
           
    }
}
